#include <iostream>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int val = 0, ListNode *nt = NULL): val(val), next(nt) {}
};

class recursive_reverse {
public:
    ListNode *reverseAll(ListNode *head) {
        if (head == NULL)
            return NULL;
        if (head->next == NULL)
            return head;
        ListNode *last = reverseAll(head->next);
        head->next->next = head;
        head->next = NULL;
        return last;
    }

    ListNode *reverseN(ListNode *head, int n) {
        if (n == 1) {
            // 当反转到第n个节点时，记录下第n+1个节点
            successor = head->next;
            return head;
        }
        // 反转后面n-1个节点
        ListNode *last = reverseN(head->next, n - 1);
        head->next->next = head;
        // head的next改为第n+1个节点
        head->next = successor;
        return last;
    }

    ListNode *reverseBetween(ListNode *head, int m, int n) {
        if (m == 1) {
            return reverseN(head, n);
        }
        head->next = reverseBetween(head->next, m - 1, n - 1);
        return head;
    }
private:
    ListNode *successor;
};

class loop_reverse {
public:
    ListNode *reverseBetween(ListNode *head, int m, int n) {
        if (head == NULL || head->next == NULL) return head;
        if (m == n) return head;
        // 添加一个头节点
        ListNode *firstNode = new ListNode(-1, head);
        ListNode *cur = head, *pre = firstNode;
        int i = 1;
        // 移动到第m-n节点区间
        for (i = 1; i < m; i++) {
            pre = cur;
            cur = cur->next;
        }
        // 存下当前pre和cur位置
        ListNode *t1 = pre;
        ListNode *t2 = cur;
        // 对于区间内节点反转
        while (i++ <= n) {
            ListNode *temp = cur->next;
            cur->next = pre;
            pre = cur;
            cur = temp;
        }
        // 将前驱后驱节点进行连接
        t1->next = pre;
        t2->next = cur;

        return firstNode->next;
    }
};

class reverse_by_k_numbers {
public:
    ListNode *reverse(ListNode *head, ListNode *tail) {
        ListNode *pre, *cur, *next;
        pre = NULL;
        cur = next = head;

        while (cur != tail) {
            next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

    ListNode *reverseGroup(ListNode *head, int k) {
        if (head == NULL) return NULL;
        ListNode *left, *right;
        left = right = head;

        for (int i = 0; i < k; i++) {
            // 剩下的不足k个，直接返回head (base case)
            if (right == NULL) return head;
            right = right->next;
        }

        // 反转[left, tail)区间内的节点，然后递归反转
        ListNode *newHead = reverse(left, right);
        left->next = reverseGroup(right, k);

        return newHead;
    }
};


